Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/misc/volume16/sipp2.0/part03

Internet Message Format | 1991-01-02 | 54.2 KB

From: [e-mail] (Kent Landfield)
Newsgroups: comp.sources.misc
Subject: v16i007:  sipp 2.0 - a library for 3D graphics, Part03/06
Message-ID: <[e-mail]>
Date: 3 Jan 91 06:57:50 GMT
Approved: [e-mail]
X-Checksum-Snefru: 1c94c058 ced62359 6fbe10b6 18ea05a5

Submitted-by: [e-mail] (Inge Wallin)
Posting-number: Volume 16, Issue 7
Archive-name: sipp2.0/part03

#!/bin/sh
# This is part 03 of sipp-2.0
# ============= libsipp/sipp.c ==============
if test ! -d 'libsipp'; then
    echo 'x - creating directory libsipp'
    mkdir 'libsipp'
fi
if test -f 'libsipp/sipp.c' -a X"$1" != X"-c"; then
    echo 'x - skipping libsipp/sipp.c (File already exists)'
else
echo 'x - extracting libsipp/sipp.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'libsipp/sipp.c' &&
/*
X * sipp - SImple Polygon Processor
X *
X *  A general 3d graphic package
X *
X *  Copyright Jonas Yngvesson  ([e-mail]) 1988/89/90
X *            Inge Wallin      ([e-mail])         1990
X *
X * This program is free software; you can redistribute it and/or modify
X * it under the terms of the GNU General Public License as published by
X * the Free Software Foundation; either version 1, or any later version.
X * This program is distributed in the hope that it will be useful,
X * but WITHOUT ANY WARRANTY; without even the implied warranty of
X * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
X * GNU General Public License for more details.
X * You can receive a copy of the GNU General Public License from the
X * Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
X * See the README for more information.
X *
X * Revision history:
X *
X * 901219  At last! 2.0 is out of the bag. And right in time for X-mas :-)
X *         *Major* rewrite. A new level in the object hierarchy introduced.
X *         An object is now a collection of surfaces and other objects
X *         (subobjects). This allows creation of complex composite objects.
X *         Objects in the hierarchy have coupled transformations.
X *         The old "Object" is now, more appropriately, called Surface.
X *         A fatal bug in the viewing transformation fixed.
X *         Objects and surfaces have internal reference counters so deletion
X *         won't leave dangling references in an hierachy.
X *         The code is now almost readable.
X *         Images format changed to PPM since much more applications
X *         exists that can handle that format.
X *         The shader package is extended and a package with functions
X *         to create geometric primitives as objects is provided.
X *
X * 901030  More general shader interface. The simple internal shader
X *         was moved out of sipp into its own file. Several shaders
X *         provided together with it in a "shader package".
X *
X * 900712  Major code beautifying, quite a lot left to do though...
X *         Typedefs instead of raw structures,
X *         much better typenames, lots of comments added (probably
X *         not enough though). Split into a few header files and
X *         a source file. More portable interface.
X *
X * 891124  Made the object representation independent of the
X *         illumination model used. A user can now supply his
X *         own surface description and shading function.
X *         Added support for texture mapping (both solid and 2d).
X *         No texture mapping is built into the internal shader though.
X *
X * 891120  Added colour. New illumination model. Simple antialiasing
X *         with double oversampling and a box filter.
X *
X * 891028  Converted from sippuz to sipp. Z-buffer changed
X *         to scan-line z-buffer.
X *         Phong-shading.
X *         The stack notion introduced.
X *         Changed fixed viewpoint to a user defined one.
X *         World coordinates and picture resolution can be chosen
X *         freely.
X *
X * 881128  Converted from Pascal to C. Gouraud shading. Redesign of the
X *         data structures.
X *
X * 88????  Original program "sippuz - simple polygon processing using a
X *         z-buffer", written in Hedrick Pascal on a DEC-20 system
X *         running TOPS-20. Greyscales only. Flat shading.
X */
X
X
#include <stdio.h>
#include <math.h>
#include <malloc.h>
#ifndef NOMEMCPY
#include <memory.h>
#endif
#include <xalloca.h>
X
#include <sipp.h>
#include <sipptypes.h>
#include <geometric.h>
X
X
#define VERSION "2.0"
X
#define ZCLIPF 100.0        /* Magic number used when defining hither & yon */
X
X
X
/*
X * Global variables.
X */
static Vertex      *vertex_tree;     /* Vertex tree for current object. */
static Vertex_ref  *vertex_stack;    /* Vertex stack for current polygon. */
static Vertex_ref  *vstack_bottom;   /* Last entry in vertex stack. */
static Polygon     *poly_stack;      /* Polygon stack for current object. */
static Inst_object *object_db;       /* Object database. */
static Lightsource *lightsrc_stack;  /* Lightsource list. */
static Bucket      *y_bucket;        /* Y-bucket for edge lists. */
static double       dist_limit;      /* Minimal distance between two      */
X                                     /* vertices without them being       */
X                                     /* considered to be the same vertex. */
static int          first_vertex;    /* Used when determining if we are   */
X                                     /* installing the first vertex in an */
X                                     /* object. *Not* a boolean!          */
X
/*
X * Stack of transformation matrices used
X * when traversing an object hierarchy.
X */
static struct tm_stack_t {
X    Transf_mat         mat;
X    struct tm_stack_t *next;
} *tm_stack;
X
static Transf_mat      curr_mat;     /* Current transformation matrix */
X
static Transf_mat      ident_matrix = {{        /* Unit tranfs. matrix */
X                           { 1.0, 0.0, 0.0 },
X                           { 0.0, 1.0, 0.0 },
X                           { 0.0, 0.0, 1.0 },
X                           { 0.0, 0.0, 0.0 }
X                       }};
X
X
/*
X * Viewpoint definition
X */
static struct {
X    double x0, y0, z0;    /* viewpoint position */
X    double x, y, z;       /* point to look at */
X    Vector vec;           /* vector from point to eye, used in shading calc. */
X    Vector up;            /* Up direction in the view */
X    double focal_ratio;
} camera;
X
X
X
/*======================== "Safe" malloc ================================*/
static char *
smalloc(size)
X    int size;
{
X    char *p;
X
X    p = (char *)malloc(size);
X    if (p == NULL) {
X        fprintf(stderr, "Out of virtual memory.\n");
X        exit(1);
X    }
X
X    return p;
}
X
X
X
/*================ Functions that handles lightsources ==================*/
X
/*
X * Define a new lightsource in the scene.
X */
void
lightsource_push(x, y, z, intensity)
X    double  x, y, z, intensity;
{
X    double       norm;
X    Lightsource *lp;
X
X    norm = sqrt(x * x + y * y + z * z);
X    lp = (Lightsource *)smalloc(sizeof(Lightsource));
X    lp->dir.x = x / norm;
X    lp->dir.y = y / norm;
X    lp->dir.z = z / norm;
X    lp->intensity = intensity;
X    lp->next = lightsrc_stack;
X    lightsrc_stack = lp;
}
X
X
X
/*================ Functions that handles the viewpoint ==================*/
X
/*
X * Calculate the vector from the point of interest
X * to the viewpoint. The shaders needs this vector normalized
X * while the view coordinate transformation needs it
X * non normalized, therefore we need this routine to
X * recalculate the non normalized value.
X */
static void
view_vec_eval()
{
X    MakeVector(camera.vec,
X               camera.x0 - camera.x,
X               camera.y0 - camera.y,
X               camera.z0 - camera.z);
}
X
X
X
/*
X * Define the viewpoint.
X */
void
view_from(x0, y0, z0)
X    double x0, y0, z0;
{
X    camera.x0 = x0;
X    camera.y0 = y0;
X    camera.z0 = z0;
X    view_vec_eval();
}
X
X
/*
X * Define the point that we are looking at.
X */
void
view_at(x, y, z)
X    double x, y, z;
{
X    camera.x = x;
X    camera.y = y;
X    camera.z = z;
X    view_vec_eval();
}
X
X
/*
X * Define the "up" direction of the view (well, rather the y-z plane).
X */
void
view_up(x, y, z)
X    double x, y, z;
{
X    MakeVector(camera.up, x, y, z);
}
X
X
/*
X * Set the focal ratio for the "camera".
X */
void
view_focal(ratio)
X    double ratio;
{
X    camera.focal_ratio = ratio;
}
X
X
/*
X * Set all viewpoint parameters in one call.
X */
void
viewpoint(x0, y0, z0, x, y, z, ux, uy, uz, ratio)
X    double x0, y0, z0, x, y, z, ux, uy, uz, ratio;
{
X    camera.x0 = x0;
X    camera.y0 = y0;
X    camera.z0 = z0;
X    camera.x = x;
X    camera.y = y;
X    camera.z = z;
X    MakeVector(camera.up, ux, uy, uz);
X    camera.focal_ratio = ratio;
X    view_vec_eval();
}
X
X
X
/*============= Functions that handles the object database ================*/
X
/*
X * Search for a vertex in a vertex tree. Vertices are asumed
X * to be equal if they differ less than dist_limit in all directions.
X *
X * If the vertex is not found, install it in the tree.
X */
static Vertex *
vertex_lookup(x, y, z, u, v, w, p)
X    double   x, y, z, u, v, w;
X    Vertex **p;
{
X    double  xdist, ydist, zdist;
X
X    if (*p == NULL) {
X        *p = (Vertex *)smalloc(sizeof(Vertex));
X        (*p)->x = x;
X        (*p)->y = y;
X        (*p)->z = z;
X        (*p)->a = 0;
X        (*p)->b = 0;
X        (*p)->c = 0;
X        (*p)->u = u;
X        (*p)->v = v;
X        (*p)->w = w;
X        (*p)->big = NULL;
X        (*p)->sml = NULL;
X        return *p;
X    } else if ((xdist = x - ((*p)->x)) > dist_limit) {
X        return (vertex_lookup(x, y, z, u, v, w, &((*p)->big)));
X    } else if (xdist < -dist_limit) {
X        return (vertex_lookup(x, y, z, u, v, w, &((*p)->sml)));
X    } else if ((ydist = y - ((*p)->y)) > dist_limit) {
X        return (vertex_lookup(x, y, z, u, v, w, &((*p)->big)));
X    } else if (ydist < -dist_limit) {
X        return (vertex_lookup(x, y, z, u, v, w, &((*p)->sml)));
X    } else if ((zdist = z - ((*p)->z)) > dist_limit) {
X        return (vertex_lookup(x, y, z, u, v, w, &((*p)->big)));
X    } else if (zdist < -dist_limit) {
X        return (vertex_lookup(x, y, z, u, v, w, &((*p)->sml)));
X    } else {
X        return *p;
X    }
}
X
X
/*
X * Push a vertex on the vertex stack (without texture coordinates).
X */
void
vertex_push(x, y, z)
X    double  x, y, z;
{
X    vertex_tx_push(x, y, z, (double)0.0, (double)0.0, (double)0.0);
}
X
X
/*
X * Push a vertex on the vertex stack (with texture coordinates).
X */
void
vertex_tx_push(x, y, z, u, v, w)
X    double  x, y, z, u, v, w;
{
X    Vertex_ref *vref;
X
X   /*
X    * To get a reasonable dist_limit we use the following "heuristic"
X    * value:
X    * The distance between the first two vertices installed in
X    * the scene, multiplied by the magic number 1e-10, unless
X    * they are the same vertex. In that case 1e-10 is used until
X    * we get a vertex that differs from the first.
X    */
X    if (!first_vertex)
X        first_vertex++;
X    else if (first_vertex == 1) {
X        dist_limit = sqrt((x - vertex_tree->x) * (x - vertex_tree->x)
X                        + (y - vertex_tree->y) * (y - vertex_tree->y)
X                        + (z - vertex_tree->z) * (z - vertex_tree->z))
X                   * 1e-10;                      /* Magic!!! */
X        if (dist_limit != 0.0)
X            first_vertex++;
X        else
X            dist_limit = 1e-10;                  /* More Magic */
X    }
X    vref = (Vertex_ref *)smalloc(sizeof(Vertex_ref));
X    if (vertex_stack == NULL) {
X        vertex_stack = vref;
X    } else {
X        vstack_bottom->next = vref;
X    }
X    vstack_bottom = vref;
X    vref->vertex = vertex_lookup(x, y, z, u, v, w, &vertex_tree);
X    vref->next = NULL;
}
X
X
/*
X * Push a polygon on the polygon stack. Empty the vertex stack afterwards.
X */
void
polygon_push()
{
X    Polygon *polyref;
X
X    if (vertex_stack != NULL) {
X        polyref = (Polygon *)smalloc(sizeof(Polygon));
X        polyref->vertices = vertex_stack;
X        polyref->backface = 0;
X        polyref->next = poly_stack;
X        poly_stack = polyref;
X        vertex_stack = NULL;
X    }
}
X
X
/*
X * Create a surface of all polygons in the polygon stack.
X * Empty the polygon stack afterwards.
X */
Surface *
surface_create(surf_desc, shader)
X    void   *surf_desc;
X    Shader *shader;
{
X    Surface *surfref;
X
X    if (poly_stack != NULL) {
X        surfref = (Surface *)smalloc(sizeof(Surface));
X        surfref->vertices = vertex_tree;
X        surfref->polygons = poly_stack;
X        surfref->surface = surf_desc;
X        surfref->shader = shader;
X        surfref->ref_count = 0;
X        surfref->next = NULL;
X        vertex_tree = NULL;
X        poly_stack = NULL;
X        first_vertex = 0;
X        return surfref;
X    } else
X        return NULL;
}
X
X
/*
X * Create a surface to be shaded with the simple shader.
X */
Surface *
surface_basic_create(ambient, red, grn, blu, specular, c3)
X    double ambient, red, grn, blu, specular, c3;
{
X    Surf_desc *surf_desc;
X
X    surf_desc = (Surf_desc *)smalloc(sizeof(Surf_desc));
X    surf_desc->ambient = ambient;
X    surf_desc->color.red = red;
X    surf_desc->color.grn = grn;
X    surf_desc->color.blu = blu;
X    surf_desc->specular = specular;
X    surf_desc->c3 = c3;
X    return surface_create(surf_desc, basic_shader);
}
X
X
/*
X * Set SURFACE to be shaded with the shading function SHADER
X * using the surface description SURF_DESC.
X */
void
surface_set_shader(surface, surf_desc, shader)
X    Surface *surface;
X    void    *surf_desc;
X    Shader  *shader;
{
X
X    if (surface != NULL) {
X        surface->surface = surf_desc;
X        surface->shader = shader;
X    }
}
X
X
/*
X * Set SURFACE to be shaded with the simple shader.
X */
void
surface_basic_shader(surface, ambient, red, grn, blu, specular, c3)
X    Surface *surface;
X    double  ambient, red, grn, blu, specular, c3;
{
X    Surf_desc *surf_desc;
X
X    surf_desc = (Surf_desc *)smalloc(sizeof(Surf_desc));
X    surf_desc->ambient = ambient;
X    surf_desc->color.red = red;
X    surf_desc->color.grn = grn;
X    surf_desc->color.blu = blu;
X    surf_desc->specular = specular;
X    surf_desc->c3 = c3;
X    surface_set_shader(surface, surf_desc, basic_shader);
}
X
X
X
/*
X * Copy a vertex tree.
X */
static Vertex *
copy_vertices(vp)
X    Vertex *vp;
{
X    Vertex *tmp;
X
X    if (vp == NULL)
X        return NULL;
X    tmp = (Vertex *)smalloc(sizeof(Vertex));
X    *tmp = *vp;
X    tmp->big = copy_vertices(vp->big);
X    tmp->sml = copy_vertices(vp->sml);
X    return tmp;
}
X
X
/*
X * We have a list of vertes references, each pointing into a certain
X * vertex tree. Create a new list with pointers into a copy of the
X * first vertex tree.
X */
static Vertex_ref *
copy_vlist(vp, surface)
X    Vertex_ref *vp;
X    Surface    *surface;
{
X    Vertex_ref *tmp;
X
X    if (vp == NULL)
X        return NULL;
X    tmp = (Vertex_ref *)smalloc(sizeof(Vertex_ref));
X    tmp->vertex = vertex_lookup(vp->vertex->x, vp->vertex->y, vp->vertex->z,
X                                vp->vertex->u, vp->vertex->v, vp->vertex->w,
X                                &(surface->vertices));
X    tmp->next = copy_vlist(vp->next, surface);
X    return tmp;
}
X
X
/*
X * Copy a list of polygons.
X */
static Polygon *
copy_polygons(pp, surface)
X    Polygon *pp;
X    Surface *surface;
{
X    Polygon *tmp;
X
X    if (pp == NULL)
X        return NULL;
X    tmp = (Polygon *)smalloc(sizeof(Polygon));
X    tmp->vertices = copy_vlist(pp->vertices, surface);
X    tmp->next = copy_polygons(pp->next, surface);
X    return tmp;
}
X
X
/*
X * Copy a list of surfaces. All polygons and vertices are copied but
X * the shader and surface descriptions are the same as in the
X * original surfaces.
X */
static Surface *
surface_copy(surface)
X    Surface  *surface;
{
X    Surface  *newsurf;
X
X    if (surface != NULL) {
X        newsurf = (Surface *)smalloc(sizeof(Surface));
X        if (newsurf == NULL) {
X            return NULL;
X        }
X        memcpy(newsurf, surface, sizeof(Surface));
X        newsurf->vertices = copy_vertices(surface->vertices);
X        newsurf->polygons = copy_polygons(surface->polygons, newsurf);
X        newsurf->ref_count = 1;
X        newsurf->next = surface_copy(surface->next);
X        return newsurf;
X    } else {
X        return NULL;
X    }
}
X
X
/*
X * Delete a vertex tree.
X */
static void
delete_vertices(vtree)
X    Vertex **vtree;
{
X    if (*vtree != NULL) {
X        delete_vertices(&((*vtree)->big));
X        delete_vertices(&((*vtree)->sml));
X        free(*vtree);
X        *vtree = NULL;
X    }
}
X
X
/*
X * Delete a surface list.
X */
static void
surface_delete(surface)
X    Surface *surface;
{
X    Vertex_ref *vref1, *vref2;
X    Polygon    *polyref1, *polyref2;
X
X    if (surface != NULL) {
X        if (--surface->ref_count == 0) {
X            if (surface->next != NULL) {
X                surface_delete(surface->next);
X            }
X            polyref2 = surface->polygons;
X            while (polyref2 != NULL) {
X                vref2 = polyref2->vertices;
X                while (vref2 != NULL) {
X                    vref1 = vref2;
X                    vref2 = vref2->next;
X                    free(vref1);
X                }
X                polyref1 = polyref2;
X                polyref2 = polyref2->next;
X                free(polyref1);
X            }
X            delete_vertices(&(surface->vertices));
X            free(surface);
X        }
X    }
}
X
X
/*
X * Install an object in the rendering database.
X */
static void
r_object_install(obj, obj_tree)
X    Object       *obj;
X    Inst_object **obj_tree;
{
X    if (obj != NULL) {
X        obj->ref_count++;
X        if (*obj_tree == NULL) {
X            *obj_tree = (Inst_object *)smalloc(sizeof(Inst_object));
X            (*obj_tree)->object = obj;
X            (*obj_tree)->big = NULL;
X            (*obj_tree)->sml = NULL;
X        } else if (obj > (*obj_tree)->object) {
X            r_object_install(obj, &(*obj_tree)->big);
X        } else if (obj < (*obj_tree)->object) {
X            r_object_install(obj, &(*obj_tree)->sml);
X        }
X    }
}
X
X
/*
X * Interface to r_object_install(). (Why is there no
X * subfunctions in C?...)
X */
void
object_install(obj)
X    Object *obj;
{
X    r_object_install(obj, &object_db);
}
X
X
X
/*
X * Subfunction to r_object_uninstall.
X */
static void
r_del(r, q)
X    Inst_object **r;
X    Inst_object  *q;
{
X    if ((*r)->big != NULL) {
X        r_del(&((*r)->big), q);
X    } else {
X        q->object = (*r)->object;
X        q = *r;
X        *r = (*r)->sml;
X        free(q);
X    }
}
X
X
/*
X * Delete an object from the rendering database.
X * The object itself is not deleted of course.
X */
static void
r_object_uninstall(obj, root)
X    Object       *obj;
X    Inst_object **root;
{
X    Inst_object *ptr;
X
X    if (*root == NULL) {
X        return;            /* Object is not in the tree */
X    } else if (obj < (*root)->object) {
X        r_object_uninstall(obj, &(*root)->sml);
X    } else if (obj > (*root)->object) {
X        r_object_uninstall(obj, &(*root)->big);
X    } else {
X        obj->ref_count--;
X        ptr = *root;
X        if (ptr->big == NULL) {
X            *root = ptr->sml;
X        } else if (ptr->sml == NULL) {
X            *root = ptr->big;
X        } else {
X            r_del(&ptr->sml, ptr);
X        }
X    }
}
X
X
/*
X * Interface to r_object_uninstall.
X */
void
object_uninstall(obj)
X    Object *obj;
{
X    r_object_uninstall(obj, &object_db);
}
X
X
X
/*
X * Create an empty object. Before it is rendered it
X * must get a surface or a subobject.
X */
Object *
object_create()
{
X    Object *obj;
X
X    obj = (Object *)smalloc(sizeof(Object));
X    obj->surfaces = NULL;
X    obj->sub_obj = NULL;
X    MatCopy(&obj->transf, &ident_matrix);
X    obj->ref_count = 0;
X    obj->next = NULL;
X
X    return obj;
}
X
X
X
/*
X * Copy the top object in an object hierarchy.
X * The new object will reference the same
X * subobjects and surfaces as the original object.
X * if REF_COUNT_UPDATE is true, the reference counts
X * in the surfaces and subobjects will be incremented.
X */
static Object *
object_copy(object, ref_count_update)
X    Object *object;
X    bool    ref_count_update;
{
X    Object *newobj;
X
X    if (object == NULL) {
X        return NULL;
X    }
X
X    if ((newobj = (Object *)smalloc(sizeof(Object))) != NULL) {
X        memcpy(newobj, object, sizeof(Object));
X        if (ref_count_update) {
X            if (newobj->sub_obj != NULL) {
X                newobj->sub_obj->ref_count++;
X            }
X            if (newobj->surfaces != NULL) {
X                newobj->surfaces->ref_count++;
X            }
X        }
X        MatCopy(&newobj->transf, &ident_matrix);
X        newobj->ref_count = 0;
X        newobj->next = NULL;
X    }
X
X    return newobj;
}
X
X
/*
X * Copy a list of objects. If SURF_COPY is true
X * the surfaces in the objects will be copied too.
X */
static Object *
object_list_copy(object, surf_copy)
X    Object *object;
X    bool    surf_copy;
{
X    Object *newobj;
X
X    if (object == NULL) {
X        return NULL;
X    }
X
X    if ((newobj = (Object *)smalloc(sizeof(Object))) != NULL) {
X        memcpy(newobj, object, sizeof(Object));
X        newobj->ref_count = 0;
X    } else {
X        return NULL;
X    }
X
X    if (surf_copy) {
X        newobj->surfaces = surface_copy(object->surfaces);
X    } else if (newobj->surfaces != NULL){
X        newobj->surfaces->ref_count++;
X    }
X
X    newobj->sub_obj = object_list_copy(object->sub_obj, surf_copy);
X    if (newobj->sub_obj != NULL) {
X        newobj->sub_obj->ref_count++;
X    }
X    newobj->next = object_list_copy(object->next, surf_copy);
X    if (newobj->next != NULL) {
X        newobj->next->ref_count++;
X    }
X
X    return newobj;
}
X
X
X
/*
X * Copy the top node of an object hierarchy. The
X * subobjects and surface references will be the
X * same as in the original.
X */
Object *
object_instance(obj)
X    Object *obj;
{
X    return object_copy(obj, TRUE);
}
X
X
X
/*
X * Copy an object hierarchy. The objects in
X * the new hierarchy will reference the same
X * surfaces as the object in
X * the old hierarchy, but all object nodes
X * will be duplicated.
X */
Object *
object_dup(object)
X    Object *object;
{
X    Object *newobj;
X
X    if ((newobj = object_copy(object, FALSE)) == NULL) {
X        return NULL;
X    }
X
X    newobj->sub_obj = object_list_copy(object->sub_obj, FALSE);
X    newobj->next = NULL;
X
X    return newobj;
}
X
X
X
/*
X * Copy an object hierarchy. All object nodes
X * and surfaces in the old hierarchy
X * will be duplicated.
X */
Object *
object_deep_dup(object)
X    Object *object;
{
X    Object *newobj;
X
X    if ((newobj = object_copy(object, FALSE)) == NULL) {
X        return NULL;
X    }
X
X    newobj->surfaces = surface_copy(object->surfaces);
X    newobj->sub_obj = object_list_copy(object->sub_obj, TRUE);
X    newobj->next = NULL;
X
X    return newobj;
}
X
X
X
/*
X * Recursively delete an object hierarchy. Reference
X * counts are decremented and if the result is zero
X * the recursion continues and the memory used is freed.
X */
static void
r_object_delete(object)
X    Object * object;
{
X    if (object != NULL) {
X        if (--object->ref_count == 0) {
X            surface_delete(object->surfaces);
X            r_object_delete(object->sub_obj);
X            r_object_delete(object->next);
X            free(object);
X        }
X    }
}
X
X
X
/*
X * Delete an object hierarchy. This is only possible
X * to do on a top level object.
X */
void
object_delete(object)
X    Object * object;
{
X    if (object != NULL) {
X        if (object->ref_count == 0) {         /* Is it a top level object? */
X            surface_delete(object->surfaces);
X            r_object_delete(object->sub_obj);
X            r_object_delete(object->next);
X            free(object);
X        }
X    }
}
X
X
X
/*
X * Add SUBOBJ as a subobject in OBJECT. SUBOBJ is appended
X * on the *end* of OBJECT's subobject list,
X * so that if SUBOBJ, for some obscure reason,
X * were the head of an object list, we don't loose
X * the rest of that list.
X * Remove SUBOBJ from the rendering database since it is no
X * longer a root object in an hierarchy.
X */
void
object_add_subobj(object, subobj)
X    Object *object, *subobj;
{
X    Object *oref;
X
X    if (object == NULL || subobj == NULL) {
X        return;
X    }
X
X    if (object->sub_obj == NULL) {
X        object->sub_obj = subobj;
X    } else {
X        oref = object->sub_obj;
X        while (oref->next != NULL) {
X            oref = oref->next;
X        }
X        oref->next = subobj;
X    }
X
X    subobj->ref_count++;
X    object_uninstall(subobj);
}
X
X
X
/*
X * Add SURFACE to the list of surfaces belonging
X * to OBJECT. SURFACE is appended on the *end* of the
X * list for the same reasons as in object_add_subobj.
X */
void
object_add_surface(object, surface)
X    Object  *object;
X    Surface *surface;
{
X    Surface *sref;
X
X    if (object == NULL || surface == NULL) {
X        return;
X    }
X
X    if (object->surfaces == NULL) {
X        object->surfaces = surface;
X    } else {
X        sref = object->surfaces;
X        while (sref->next != NULL) {
X            sref = sref->next;
X        }
X        sref->next = surface;
X    }
X
X    surface->ref_count++;
}
X
X
X
X
/*============= Functions that handles object transformations==============*/
X
/*
X * Set the transformation matrix of OBJ to MATRIX.
X */
void
object_set_transf(obj, matrix)
X    Object     *obj;
X    Transf_mat *matrix;
{
X    MatCopy(&obj->transf, matrix);
}
X
X
/*
X * Set the transformation matrix of OBJ to the identity matrix.
X */
void
object_clear_transf(obj)
X    Object *obj;
{
X    MatCopy(&obj->transf, &ident_matrix);
}
X
X
/*
X * Post multiply MATRIX into the transformation matrix of OBJ.
X */
void
object_transform(obj, matrix)
X    Object     *obj;
X    Transf_mat *matrix;
{
X    mat_mul(&obj->transf, &obj->transf, matrix);
}
X
X
/*
X * Rotate the object OBJ ANG radians about the x-axis.
X */
void
object_rot_x(obj, ang)
X    Object *obj;
X    double  ang;
{
X    mat_rotate_x(&obj->transf, ang);
}
X
X
/*
X * Rotate the object OBJ ANG radians about the y-axis.
X */
void
object_rot_y(obj, ang)
X    Object *obj;
X    double  ang;
{
X    mat_rotate_y(&obj->transf, ang);
}
X
X
/*
X * Rotate the object OBJ ANG radians about the z-axis.
X */
void
object_rot_z(obj, ang)
X    Object *obj;
X    double  ang;
{
X    mat_rotate_z(&obj->transf, ang);
}
X
X
/*
X * Rotate the object OBJ ANG radians about the line defined
X * by POINT and VEC.
X */
void
object_rot(obj, point, vec, ang)
X    Object *obj;
X    Vector *point;
X    Vector *vec;
X    double  ang;
{
X    mat_rotate(&obj->transf, point, vec, ang);
}
X
X
/*
X * Scale the object OBJ with respect to the origin.
X */
void
object_scale(obj, xscale, yscale, zscale)
X    Object *obj;
X    double  xscale, yscale, zscale;
{
X    mat_scale(&obj->transf, xscale, yscale, zscale);
}
X
X
/*
X * Translate the object OBJ.
X */
void
object_move(obj, dx, dy, dz)
X    Object *obj;
X    double  dx, dy, dz;
{
X    mat_translate(&obj->transf, dx, dy, dz);
}
X
X
X
X
/*============= Functions that handles rendering of the scene==============*/
X
X
/*
X * Calculate the normal vector for all polygons in the polygon list PSTART.
X *
X * Check if the polygon is backfacing with respect to the current
X * viewpoint.
X *
X * The normalized normal is added to a normal kept at each vertex
X * in the polygon. This will produce, at each vertex, an average of the
X * normals of the adjectent plygons.
X */
static void
calc_normals(pstart, eyepoint)
X    Polygon *pstart;    /* Head of polygon list */
X    Vector   eyepoint;  /* Viewpoint transformed to local coordinate system */
{
X    Vector      normal;
X    Vertex_ref *vref1, *vref2;
X    Polygon    *polyref;
X    double      plane_const;
X
X    for (polyref = pstart; polyref != NULL; polyref = polyref->next) {
X        vref1 = polyref->vertices;
X        vref2 = vref1->next;
X
X        normal.x = normal.y = normal.z = 0.0;
X        do {
X            normal.x += ((vref1->vertex->y - vref2->vertex->y)
X                         * (vref1->vertex->z + vref2->vertex->z));
X            normal.y += ((vref1->vertex->z - vref2->vertex->z)
X                         * (vref1->vertex->x + vref2->vertex->x));
X            normal.z += ((vref1->vertex->x - vref2->vertex->x)
X                         * (vref1->vertex->y + vref2->vertex->y));
X            vref1 = vref1->next;
X            vref2 = ((vref2->next == NULL)?polyref->vertices:vref2->next);
X        } while (vref1 != NULL);
X        vecnorm(&normal);
X
X        plane_const = -(normal.x * vref2->vertex->x
X                        + normal.y * vref2->vertex->y
X                        + normal.z * vref2->vertex->z);
X        if (VecDot(eyepoint, normal) + plane_const <= 0.0) {
X            polyref->backface = TRUE;
X        } else {
X            polyref->backface = FALSE;
X        }
X
X        for (vref1 = polyref->vertices; vref1 != NULL; vref1 = vref1->next) {
X            vref1->vertex->a += normal.x;
X            vref1->vertex->b += normal.y;
X            vref1->vertex->c += normal.z;
X        }
X    }
}
X
X
X
/*
X * Walk around a polygon, create the surrounding
X * edges and sort them into the y-bucket.
X * Clip polygons in y at the same time.
X */
static void
create_edges(view_vert, yres, polygon, surface)
X    View_coord *view_vert;
X    int         yres;
X    int         polygon;
X    Surface    *surface;
{
X    Edge       *edge;
X    View_coord *view_ref, *last;
X    int         nderiv, y1, y2, ymax;
X    int         clip1, clip2;
X    double      deltay, ratio;
X    double      x1, x2, xstep;
X    double      z1, z2, zstep;
X    double      nx1, nx2, nxstep;
X    double      ny1, ny2, nystep;
X    double      nz1, nz2, nzstep;
X    double      u1, u2, ustep;
X    double      v1, v2, vstep;
X    double      w1, w2, wstep;
X
X    view_ref = last = view_vert;
X    ymax = yres - 1;
X    do {
X        view_ref = view_ref->next;
X        x1 = view_ref->x;
X        x2 = view_ref->next->x;
X        y1 = view_ref->y;
X        y2 = view_ref->next->y;
X        z1 = view_ref->z;
X        z2 = view_ref->next->z;
X        nx1 = view_ref->nx;
X        nx2 = view_ref->next->nx;
X        ny1 = view_ref->ny;
X        ny2 = view_ref->next->ny;
X        nz1 = view_ref->nz;
X        nz2 = view_ref->next->nz;
X        u1 = view_ref->u;
X        u2 = view_ref->next->u;
X        v1 = view_ref->v;
X        v2 = view_ref->next->v;
X        w1 = view_ref->w;
X        w2 = view_ref->next->w;
X        clip1 = (y1 < 0) + ((y1 > ymax) << 1);
X        clip2 = (y2 < 0) + ((y2 > ymax) << 1);
X        if (!(clip1 & clip2)) {
X            if (clip1 != 0) {
X                if (clip1 == 1)
X                    ratio = (0.0 - (double)y1) / (double)(y2 - y1);
X                else
X                    ratio = (double)(ymax - y1) / (double)(y2 - y1);
X                x1 = x1 + ratio * (x2 - x1);
X                y1 = y1 + ratio * (y2 - y1);
X                z1 = z1 + ratio * (z2 - z1);
X                nx1 = nx1 + ratio * (nx2 - nx1);
X                ny1 = ny1 + ratio * (ny2 - ny1);
X                nz1 = nz1 + ratio * (nz2 - nz1);
X                u1 = u1 + ratio * (u2 - u1);
X                v1 = v1 + ratio * (v2 - v1);
X                w1 = w1 + ratio * (w2 - w1);
X            }
X            if (clip2 != 0) {
X                if (clip2 == 1)
X                    ratio = (0.0 - (double)y2) / (double)(y1 - y2);
X                else
X                    ratio = (double)(ymax - y2) / (double)(y1 - y2);
X                x2 = x2 + ratio * (x1 - x2);
X                y2 = y2 + ratio * (y1 - y2);
X                z2 = z2 + ratio * (z1 - z2);
X                nx2 = nx2 + ratio * (nx1 - nx2);
X                ny2 = ny2 + ratio * (ny1 - ny2);
X                nz2 = nz2 + ratio * (nz1 - nz2);
X                u2 = u2 + ratio * (u1 - u2);
X                v2 = v2 + ratio * (v1 - v2);
X                w2 = w2 + ratio * (w1 - w2);
X            }
X            deltay = (double)(y2 - y1);
X            if (deltay > 0.0)
X            nderiv = 1;
X        else if (deltay < 0.0)
X            nderiv = -1;
X        else
X            nderiv = 0;
X            if (nderiv) {
X            deltay = fabs(deltay);
X                xstep = (x2 - x1) / deltay;
X                zstep = (z2 - z1) / deltay;
X                nxstep = (nx2 - nx1) / deltay;
X                nystep = (ny2 - ny1) / deltay;
X                nzstep = (nz2 - nz1) / deltay;
X                ustep = (u2 - u1) / deltay;
X                vstep = (v2 - v1) / deltay;
X                wstep = (w2 - w1) / deltay;
X                edge = (Edge *)smalloc(sizeof(Edge));
X                if (nderiv > 0) {
X                    edge->y = y2;
X                    edge->y_stop = y1;
X                    edge->x = x2;
X                    edge->z = z2;
X                    edge->nx = nx2;
X                    edge->ny = ny2;
X                    edge->nz = nz2;
X                    edge->u = u2;
X                    edge->v = v2;
X                    edge->w = w2;
X                    edge->xstep = -xstep;
X                    edge->zstep = -zstep;
X                    edge->nxstep = -nxstep;
X                    edge->nystep = -nystep;
X                    edge->nzstep = -nzstep;
X                    edge->ustep = -ustep;
X                    edge->vstep = -vstep;
X                    edge->wstep = -wstep;
X                } else {
X                    edge->y = y1;
X                    edge->y_stop = y2;
X                    edge->x = x1;
X                    edge->z = z1;
X                    edge->nx = nx1;
X                    edge->ny = ny1;
X                    edge->nz = nz1;
X                    edge->u = u1;
X                    edge->v = v1;
X                    edge->w = w1;
X                    edge->xstep = xstep;
X                    edge->zstep = zstep;
X                    edge->nxstep = nxstep;
X                    edge->nystep = nystep;
X                    edge->nzstep = nzstep;
X                    edge->ustep = ustep;
X                    edge->vstep = vstep;
X                    edge->wstep = wstep;
X                }
X            } else {
X                zstep = (z2 - z1) / fabs(x2 - x1);
X                edge = (Edge *)smalloc(sizeof(Edge));
X                edge->y = y2;
X                edge->y_stop = y1;
X                if (x1 < x2) {
X                    edge->x = x1;
X                    edge->z = z1;
X                    edge->xstep = x2;
X                    edge->zstep = zstep;
X                } else {
X                    edge->x = x2;
X                    edge->z = z2;
X                    edge->xstep = x1;
X                    edge->zstep = -zstep;
X                }
X            }
X            edge->polygon = polygon;
X            edge->surface = surface;
X            edge->next = NULL;
X            if (y_bucket[edge->y].last == NULL) {
X                y_bucket[edge->y].first = edge;
X                y_bucket[edge->y].last = edge;
X            } else {
X                y_bucket[edge->y].last->next = edge;
X                y_bucket[edge->y].last = edge;
X            }
X        }
X    } while (view_ref != last);
}
X
X
/*
X * Transform vertices into view coordinates. The transform is
X * defined in MATRIX. Store the transformed vertices in a
X * temporary list, create edges in the y_bucket.
X */
static void
transf_vertices(vertex_list, surface, matrix, tr_mat, xsiz, ysiz)
X    Vertex_ref *vertex_list;
X    Surface    *surface;
X    double      matrix[4][4];
X    Transf_mat *tr_mat;
X    double      xsiz, ysiz;
{
X    static int  polygon = 0;        /* incremented for each call to provide */
X                                    /* unique polygon id numbers */
X    Vertex_ref *vref;
X    View_coord *view_ref, *nhead, *ntail;
X    double      minsize;
X    double      w, tmp;
X    bool        first, last;
X
X    first = TRUE;
X    last = FALSE;
X    vref = vertex_list;
X    nhead = NULL;
X
X    minsize = ((xsiz > ysiz) ? ysiz : xsiz);
X
X    while ((vref != NULL) && !last) {
X
X        view_ref = (View_coord *)alloca(sizeof(View_coord));
X        last = (vref->next == NULL);
X
X        view_ref->nx = (vref->vertex->a * tr_mat->mat[0][0]
X                        + vref->vertex->b * tr_mat->mat[1][0]
X                        + vref->vertex->c * tr_mat->mat[2][0]);
X        view_ref->ny = (vref->vertex->a * tr_mat->mat[0][1]
X                        + vref->vertex->b * tr_mat->mat[1][1]
X                        + vref->vertex->c * tr_mat->mat[2][1]);
X        view_ref->nz = (vref->vertex->a * tr_mat->mat[0][2]
X                        + vref->vertex->b * tr_mat->mat[1][2]
X                        + vref->vertex->c * tr_mat->mat[2][2]);
X
X        w = vref->vertex->x * matrix[0][3] + vref->vertex->y * matrix[1][3] +
X        vref->vertex->z * matrix[2][3] + matrix[3][3];
X        view_ref->x = ((vref->vertex->x * matrix[0][0]
X                        + vref->vertex->y * matrix[1][0]
X                        + vref->vertex->z * matrix[2][0]
X                        + matrix[3][0]) * minsize / w + xsiz);
X        tmp         = ((vref->vertex->x * matrix[0][1]
X                        + vref->vertex->y * matrix[1][1]
X                        + vref->vertex->z * matrix[2][1]
X                        + matrix[3][1]) * minsize / w + ysiz) ;
X
X        view_ref->y = (int)(tmp + 0.5);
X        view_ref->z = (vref->vertex->x * matrix[0][2] + vref->vertex->y *
X                       matrix[1][2] + vref->vertex->z * matrix[2][2] +
X                       matrix[3][2]) / w;
X
X        view_ref->u = vref->vertex->u;
X        view_ref->v = vref->vertex->v;
X        view_ref->w = vref->vertex->w;
X        view_ref->next = nhead;
X        nhead = view_ref;
X
X        if (first) {
X            ntail = view_ref;
X            first = FALSE;
X        }
X        if (!last)
X            vref = vref->next;
X    }
X
X    ntail->next = nhead;
X    create_edges(nhead, (int)ysiz << 1, polygon++, surface);
}
X
X
/*
X * Initialize the scanline z-buffer and the actual picture
X * scanline buffer.
X */
static void
init_buffers(res, z_buffer, scanline)
X    int            res;
X    double        *z_buffer;
X    unsigned char *scanline;
{
X    int i;
X
#ifdef NOMEMCPY
X    bzero(scanline, res * 3);
#else
X    memset(scanline, 0, res * 3);
#endif
X    for (i = 0; i < res; i++)
X        z_buffer[i] = 2.0;
}
X
X
/*
X * Read edge pairs from the edge list EDGE_LIST. Walk along the scanline
X * and interpolate z value, texture coordinates and normal vector as
X * we go. Call the shader and write into scanline buffer according to
X * result on z-buffer test.
X */
static void
render_line(res, z_buffer, scanline, edge_list)
X    int            res;
X    double        *z_buffer;
X    unsigned char *scanline;
X    Edge          *edge_list;
{
X    double z, zstep;
X    double nx, nxstep;
X    double ny, nystep;
X    double nz, nzstep;
X    double u, ustep;
X    double v, vstep;
X    double w, wstep;
X    double ratio;
X    Color  color;
X    int    i, j, x, xstop;
X    Edge  *edgep, *next;
X
X    edgep = edge_list;
X    next = NULL;
X    while (edgep != NULL) {
X        if (edgep->y != edgep->y_stop) {
X            next = edgep->next;
X            while (next->y == next->y_stop)
X                next = next->next;
X            x = (int)(edgep->x + 0.5);
X            xstop = (int)(next->x + 0.5);
X            z = edgep->z;
X            nx = edgep->nx;
X            ny = edgep->ny;
X            nz = edgep->nz;
X            u = edgep->u;
X            v = edgep->v;
X            w = edgep->w;
X            if (x < xstop) {
X                ratio = (double)(xstop - x);
X                zstep = (next->z - z) / ratio;
X                nxstep = (next->nx - nx) / ratio;
X                nystep = (next->ny - ny) / ratio;
X                nzstep = (next->nz - nz) / ratio;
X                ustep = (next->u - u) / ratio;
X                vstep = (next->v - v) / ratio;
X                wstep = (next->w - w) / ratio;
X            } else {
X                zstep = 0.0;
X                nxstep = nystep = nzstep = 0.0;
X                ustep = vstep = wstep = 0.0;
X            }
X            for (i = x, j = i * 3; i <= xstop; i++) {
X                if ((i >= 0) && (i < res) && (z >= 0.0) && (z <= 1.0)
X                    && (z < z_buffer[i])) {
X                    (*edgep->surface->shader)
X                        (nx, ny, nz, u, v, w,
X                         camera.vec, lightsrc_stack,
X                         edgep->surface->surface, &color);
X                    scanline[j++] = (unsigned char)(color.red * 255.0 + 0.5);
X                    scanline[j++] = (unsigned char)(color.grn * 255.0 + 0.5);
X                    scanline[j++] = (unsigned char)(color.blu * 255.0 + 0.5);
X                    z_buffer[i] = z;
X                } else if (i >= res) {
X                    break;
X                } else {
X                    j += 3;
X                }
X                z += zstep;
X                nx += nxstep;
X                ny += nystep;
X                nz += nzstep;
X                u += ustep;
X                v += vstep;
X                w += wstep;
X            }
X        }
X        edgep = edgep->next;
X        if ((edgep == next) && (next != NULL))
X            edgep = edgep->next;
X    }
}
X
X
X
/*
X * Insert an edge into an edge list. Edges belonging to the same
X * polygon must be inserted sorted in x, so that edge pairs are
X * created.
X */
static Edge *
insert_edge(edge_list, edge, poly_found)
X    Edge *edge_list, *edge;
X    bool  poly_found;
{
X    if (edge_list == NULL) {
X        edge_list = edge;
X    edge->next = NULL;
X    } else if (edge_list->polygon == edge->polygon) {
X        if (edge_list->x > edge->x) {
X        edge->next = edge_list;
X        edge_list = edge;
X    } else if ((((int)(edge_list->x + 0.5)) == ((int)(edge->x + 0.5)))
X                   && (edge_list->xstep > edge->xstep)) {
X        edge->next = edge_list;
X        edge_list = edge;
X        } else {
X        edge_list->next = insert_edge(edge_list->next, edge, TRUE);
X        }
X    } else if (poly_found) {
X        edge->next = edge_list;
X        edge_list = edge;
X    } else {
X        edge_list->next = insert_edge(edge_list->next, edge, FALSE);
X    }
X
X    return edge_list;
}
X
X
X
/*
X * Merge two edge lists.
X */
static Edge *
merge_edge_lists(list1, list2)
X    Edge *list1, *list2;
{
X    Edge *eref1, *eref2, *next;
X
X    if (list2 == NULL)
X        return NULL;
X    eref1 = list1;
X    eref2 = list2;
X    do {
X        next = eref2->next;
X        eref1 = insert_edge(eref1, eref2, FALSE);
X    eref2 = next;
X    } while (eref2 != NULL);
X    return eref1;
}
X
X
X
/*
X * Allocate the needed buffers. Create a list of active edges and
X * move down the y-bucket, inserting and deleting edges from this
X * active list as we go. Call render_line for each scanline and
X * do an average filtering before writing the scanline to the result
X * file descriptor.
X */
static void
scan_and_render(xres, yres, image_file)
X    int  xres, yres;
X    FILE *image_file;
{
X    Edge          *active_list, *edgep, *edgep2;
X    double        *z_buffer;
X    unsigned char *scanline1, *scanline2, *stmp;
X    int            i, y, next_edge;
X
X    z_buffer = (double *)calloc(xres, sizeof(double));
X    scanline1 = (unsigned char *)calloc(xres * 3, sizeof(unsigned char));
X    scanline2 = (unsigned char *)calloc(xres * 3, sizeof(unsigned char));
X
X    fprintf(image_file, "P6\n");
X    fprintf(image_file, "#Image rendered with SIPP %s\n", VERSION);
X    fprintf(image_file, "%d\n%d\n255\n", xres >> 1, yres >> 1);
X
X    y = yres - 1;
X    active_list = NULL;
X    stmp = scanline1;
X
X    while (y >= 0) {
X        active_list = merge_edge_lists(active_list, y_bucket[y].first);
X        next_edge = y - 1;
X        while (next_edge >=0 && y_bucket[next_edge].first == NULL)
X            next_edge--;
X        while (y > next_edge) {
X            init_buffers(xres, z_buffer, stmp);
X            render_line(xres, z_buffer, stmp, active_list);
X            if (stmp == scanline1)
X                stmp = scanline2;
X            else {
X                for (i = 0; i < (xres * 3); i += 6) {
X                    scanline1[i >> 1] = (scanline1[i] +
X                                         scanline1[i + 3] +
X                                         scanline2[i] +
X                                         scanline2[i + 3]) >> 2;
X                    scanline1[(i >> 1) + 1] = (scanline1[i + 1] +
X                                               scanline1[i + 4] +
X                                               scanline2[i + 1] +
X                                               scanline2[i + 4]) >> 2;
X                    scanline1[(i >> 1) + 2] = (scanline1[i + 2] +
X                                               scanline1[i + 5] +
X                                               scanline2[i + 2] +
X                                               scanline2[i + 5]) >> 2;
X                }
X                fwrite(scanline1, (xres >> 1) * 3, 1, image_file);
X                fflush(image_file);
X                stmp = scanline1;
X            }
X        if (active_list != NULL) {
X            edgep2 = active_list;
X            edgep = active_list->next;
X            while (edgep != NULL)
X                if (edgep->y <= (edgep->y_stop + 1)) {
X                        edgep2->next = edgep->next;
X                free(edgep);
X                    edgep = edgep2->next;
X            } else {
X                edgep2 = edgep;
X                edgep = edgep->next;
X            }
X              if (active_list->y <= (active_list->y_stop + 1)) {
X                edgep = active_list;
X            active_list = active_list->next;
X                free(edgep);
X            }
X            edgep = active_list;
X            while (edgep != NULL) {
X                edgep->y--;
X            edgep->x += edgep->xstep;
X            edgep->z += edgep->zstep;
X            edgep->nx += edgep->nxstep;
X            edgep->ny += edgep->nystep;
X            edgep->nz += edgep->nzstep;
X            edgep->u += edgep->ustep;
X            edgep->v += edgep->vstep;
X            edgep->w += edgep->wstep;
X            edgep = edgep->next;
X            }
X        }
X        y--;
X    }
X    }
X    free(z_buffer);
X    free(scanline1);
X    free(scanline2);
}
X
X
X
/*
X * Reset the averaged normals in the vertex tree P.
X */
static void
reset_normals(vref)
X    Vertex *vref;
{
X    if (vref != NULL) {
X        vref->a = 0;
X        vref->b = 0;
X        vref->c = 0;
X        reset_normals(vref->big);
X        reset_normals(vref->sml);
X    }
}
X
X
X
/*
X * Build a transformation matrix for transformation
X * into view coordinates. Perpective transformation
X * is also included
X */
static void
get_view_transf(mat)
X    double mat[4][4];
{
X    Vector tmp;
X    double transl[3];
X    double vy, vz;
X    double hither, yon;
X    double alfa, beta;
X    int i, j;
X
X    /*
X     * First we need a translation so the origo
X     * of the view coordinat system is placed
X     * in the viewpoint.
X     */
X    transl[0] = -camera.x0;
X    transl[1] = -camera.y0;
X    transl[2] = -camera.z0;
X
X    /*
X     * Then we need a rotation that makes the
X     * up-vector point up, and alignes the sightline
X     * with the z-axis.
X     * This code might seem magic but the algebra behind
X     * it can be found in Jim Blinn's Corner in IEEE CG&A July 1988
X     */
X    VecCopy(tmp, camera.vec);
X    VecNegate(tmp);
X    vecnorm(&tmp);
X    vecnorm(&camera.up);
X    vz = VecDot(tmp, camera.up);
X    if ((vz * vz) > 1.0) {        /* this should not happen, but... */
X        vz = 1.0;
X    } else {
X        vy = sqrt(1.0 - vz * vz);
X        if (vy == 0.0) {          /* oops, the world collapses... */
X            vy = 1.0e10;
X            vz = 1.0;
X        } else {
X            vy = 1.0 / vy;
X        }
X    }
X
X    mat[0][2] = tmp.x;
X    mat[1][2] = tmp.y;
X    mat[2][2] = tmp.z;
X
X    VecScalMul(tmp, vz, tmp);
X    VecSub(tmp, camera.up, tmp);
X    mat[0][1] = tmp.x * vy;
X    mat[1][1] = tmp.y * vy;
X    mat[2][1] = tmp.z * vy;
X
X    mat[0][0] = mat[1][1] * mat[2][2] - mat[1][2] * mat[2][1];
X    mat[1][0] = mat[2][1] * mat[0][2] - mat[2][2] * mat[0][1];
X    mat[2][0] = mat[0][1] * mat[1][2] - mat[0][2] * mat[1][1];
X
X    /*
X     * Install the translation into the matrix.
X     * Note that it is PRE-multiplied into the matrix.
X     */
X    for (i = 0; i < 3; i++) {
X        mat[3][i] = 0.0;
X        for (j = 0; j < 3; j++) {
X            mat[3][i] += transl[j] * mat[j][i];
X        }
X    }
X
X    /*
X     * Include the perspective transformation
X     * using heuristic values for hither and yon.
X     */
X    hither = VecLen(camera.vec) / ZCLIPF;
X    yon    = VecLen(camera.vec) * ZCLIPF;
X    alfa = camera.focal_ratio / (1.0 - hither / yon);
X    beta = -hither * alfa;
X
X    mat[0][3] = mat[0][2] * camera.focal_ratio;
X    mat[0][2] *= alfa;
X    mat[1][3] = mat[1][2] * camera.focal_ratio;
X    mat[1][2] *= alfa;
X    mat[2][3] = mat[2][2] * camera.focal_ratio;
X    mat[2][2] *= alfa;
X    mat[3][3] = mat[3][2] * camera.focal_ratio;
X    mat[3][2] = mat[3][2] * alfa + beta;
X
X    /*
X     * Since the screen coordinates are defined in a left handed
X     * coordinate system, we must switch the sign of the first
X     * column in the matrix to get appropriate signs of x-values.
X     */
X    mat[0][0] = -mat[0][0];
X    mat[1][0] = -mat[1][0];
X    mat[2][0] = -mat[2][0];
X    mat[3][0] = -mat[3][0];
}
X
X
/*
X * Free the memory used by an edge list.
X */
static void
delete_edges(edge_list)
X    Edge *edge_list;
{
X    Edge *edgeref1, *edgeref2;
X
X    edgeref1 = edge_list;
X    while (edgeref1 != NULL) {
X        edgeref2 = edgeref1->next;
X        free(edgeref1);
X        edgeref1 = edgeref2;
X    }
}
X
X
X
/*
X * Push the current transformation matrix on the matrix stack.
X */
static void
matrix_push()
{
X    struct tm_stack_t *new_tm;
X
X    new_tm = (struct tm_stack_t *)smalloc(sizeof(struct tm_stack_t));
X    MatCopy(&new_tm->mat, &curr_mat);
X    new_tm->next = tm_stack;
X    tm_stack     = new_tm;
}
X
X
/*
X * Pop the top of the matrix stack and make
X * it the new current transformation matrix.
X */
static void
matrix_pop()
{
X    struct tm_stack_t *tmp;
X
X    MatCopy(&curr_mat, &tm_stack->mat);
X    tmp = tm_stack;
X    tm_stack = tm_stack->next;
X    free(tmp);
}
X
X
X
/*
X * Traverse an object hierarchy, transform each object
X * according to its transformation matrix.
X * Transform all polygons in the object to view coordinates.
X * Build the edge lists in y_bucket.
X */
static void
traverse_object_tree(object, glob_view_mat, xres, yres)
X    Object *object;
X    double  glob_view_mat[4][4];
X    int     xres, yres;
{
X    Object  *objref;
X    Surface *surfref;
X    Polygon *polyref;
X    Vector   eyepoint, tmp;
X    double   loc_view_mat[4][4];
X
X
X    if (object == NULL) {
X        return;
X    }
X
X    for (objref = object; objref != NULL; objref = objref->next) {
X
X        matrix_push();
X        mat_mul(&curr_mat, &objref->transf, &curr_mat);
X        mat_mul34(loc_view_mat, &curr_mat, glob_view_mat);
X
X        tmp.x = camera.x0;
X        tmp.y = camera.y0;
X        tmp.z = camera.z0;
X
X        /*
X         * Do an inverse transformation of the viewpoint to use
X         * when doing backface culling (in calc_normals()).
X         */
X        tmp.x -= curr_mat.mat[3][0];
X        tmp.y -= curr_mat.mat[3][1];
X        tmp.z -= curr_mat.mat[3][2];
X        eyepoint.x = (tmp.x * curr_mat.mat[0][0] + tmp.y * curr_mat.mat[0][1]
X                      + tmp.z * curr_mat.mat[0][2]);
X        eyepoint.y = (tmp.x * curr_mat.mat[1][0] + tmp.y * curr_mat.mat[1][1]
X                      + tmp.z * curr_mat.mat[1][2]);
X        eyepoint.z = (tmp.x * curr_mat.mat[2][0] + tmp.y * curr_mat.mat[2][1]
X                      + tmp.z * curr_mat.mat[2][2]);
X
X        for (surfref = objref->surfaces; surfref != NULL;
X             surfref = surfref->next) {
X
X            calc_normals(surfref->polygons, eyepoint);
X
X            for (polyref = surfref->polygons; polyref != NULL;
X                 polyref = polyref->next) {
X
X                if (!polyref->backface) {
X                    transf_vertices(polyref->vertices, surfref, loc_view_mat,
X                                    &curr_mat, (double)xres, (double)yres);
X                }
X
X            }
X            reset_normals(surfref->vertices);
X
X        }
X        traverse_object_tree(objref->sub_obj, glob_view_mat, xres, yres);
X        matrix_pop();
X    }
}
X
X
X
/*
X * Recursively traverse the rendering database (preorder).
X * Call traverse_object_tree for each object.
X */
static void
traverse_object_db(obj_root, view_mat, xres, yres)
X    Inst_object *obj_root;
X    double       view_mat[4][4];
X    int          xres, yres;
{
X    if (obj_root != NULL) {
X        traverse_object_tree(obj_root->object, view_mat, xres, yres);
X        traverse_object_db(obj_root->sml, view_mat, xres, yres);
X        traverse_object_db(obj_root->big, view_mat, xres, yres);
X    }
}
X
X
X
X
/*
X * "Main" function in rendering. Allocate y-bucket, transform vertices
X * into viewing coordinates, make edges and sort them into the y-bucket.
X * Call scan_and_render to do the real work.
X */
void
render_image(xres, yres, image_file)
X    int   xres, yres;
X    FILE *image_file;
{
X    double      matrix[4][4];
X    int         i;
X
X    y_bucket = (Bucket *)calloc(yres << 1, sizeof(Bucket));
X
X    get_view_transf(matrix);
X    MatCopy(&curr_mat, &ident_matrix);
X
X    traverse_object_db(object_db, matrix, xres, yres);
X
X    vecnorm(&camera.vec);
X    scan_and_render(xres << 1, yres << 1, image_file);
X    view_vec_eval();
X
X    for (i = 0; i < (yres << 1); i++)
X        delete_edges(y_bucket[i].first);
X    free(y_bucket);
}
X
X
X
/*============= Functions that handles global initializations==============*/
X
/*
X * Necessary initializations.
X */
void
sipp_init()
{
X    vertex_tree    = NULL;
X    vertex_stack   = NULL;
X    poly_stack     = NULL;
X    object_db      = NULL;
X    lightsrc_stack = NULL;
X    first_vertex   = 0;
X    viewpoint(0.0, 0.0, 10.0,  0.0, 0.0, 0.0,  0.0, 1.0, 0.0,  0.25);
}
SHAR_EOF
chmod 0644 libsipp/sipp.c ||
echo 'restore of libsipp/sipp.c failed'
Wc_c="`wc -c < 'libsipp/sipp.c'`"
test 52154 -eq "$Wc_c" ||
    echo 'libsipp/sipp.c: original size 52154, current size' "$Wc_c"
fi
true || echo 'restore of libsipp/sipp.h failed'
echo End of part 3, continue with part 4
exit 0

--
Inge Wallin               | Thus spake the master programmer:               |
                          |      "After three days without programming,     |
[e-mail]          |       life becomes meaningless."                |
                          | Geoffrey James: The Tao of Programming.         |


exit 0 # Just in case...
--
Kent Landfield                   INTERNET: [e-mail]
Sterling Software, IMD           UUCP:     uunet!sparky!kent
Phone:    [phone]         FAX:      [phone]
Please send comp.sources.misc-related mail to [e-mail].